A multi-threaded processor is a microprocessor with execution units, caches and memories, etc. as per any other processor, but that additionally incorporates the concept of multiple threads of execution. A thread of execution consists of a stream of instructions acting upon the resources of the microprocessor, some of which are private to that specific thread and some of which may be shared between threads. Resources include registers, bandwidth and space in the cache or memories. FIG. 1 is a schematic illustration of a multithreaded microprocessor core, known in the art. In a multithreaded processor core as shown in FIG. 1, a number of threads 2 can operate in parallel, subject to their ability to issue instructions via the thread instruction scheduler 1. The threads may be given a priority order to allow the scheduler to determine which instructions to issue first.
It is possible for the processor to issue instructions from multiple threads in the same clock cycle provided that they do not use the same resources, such as the same data cache 3, at the same time. The scheduler must be configured to determine which instructions can be issued together in each clock cycle.
Speculative instructions are a particular type of instruction. The concept of speculative instruction fetching and issue is well understood in the field of microprocessors. Speculative instruction fetch and issue takes the form of making a prediction of the outcome of an earlier program instruction and then fetching and issuing instructions based on that prediction before it is known whether the prediction was correctly made. The most common example of an action to predict the outcome is of a branch in a program, where a choice is made as to what code path to take based on a conditional test. Other examples include return predictions and jump predictions. If it is later determined that the prediction was correct, the processor continues. If it is determined that the prediction was incorrect, then it is necessary to delete the predicted instructions and their side effects, and restart the instruction fetch and issue from the newly determined instruction fetch address.
The term speculative is used because the processor needs to act in advance of knowing the outcome of any recently issued instructions. For example, a branch may well follow immediately after a compare or condition testing instruction. In a pipelined processor the pipeline may be many stages long and the result of the condition test typically produces a result a long way down the pipeline. However, branches directly affect instruction fetch and will therefore have an impact right at the start of the pipeline. This leads to a bubble or stall as the branch has to wait for the condition test result to be known, and the alternative to this wait is to guess which branch is likely to be taken and take that guess as the route to follow until it is known whether the guess was right or wrong. The instructions fetched and/or issued between guessing and knowing the correctness of that guess are not necessarily correct and may have to be unwound—hence the term speculative. Guesses are either made based upon simple rules (e.g. backwards branches taken, forwards branches not taken) or historical data that indicates what a given section of code did most commonly in the past.
As used herein, the term “speculative instruction” means an instruction fetched and/or issued that may not be necessary, because the outcome of an earlier program instruction is not yet known.
The present invention deals with the problem of how to schedule the issue of speculative instructions in a processor that can issue instructions from multiple threads in the same clock cycle.